import java.util.LinkedList;
import java.util.Queue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-05-25
 * Time: 21:21
 */

public class MaxQueue {

    public Queue<Integer> queue;
    // 一个单调队列
    public LinkedList<Integer> maxQueue;
    public MaxQueue() {
        this.queue = new LinkedList<>();
        this.maxQueue = new LinkedList<>();
    }

    public int max_value() {
        if (maxQueue.isEmpty()){
            return -1;
        }
        return maxQueue.peekFirst();
    }

    public void push_back(int value) {
        queue.add(value);
//         一个数字加入队列后
//         它前面比它小的值是不会影响从上一个最大值到当前数字的这个区间中的最大值
//         所以要将这个数字前面的比他小的值全部删除
        while (!maxQueue.isEmpty() && maxQueue.peekLast() < value){
            maxQueue.pollLast();
        }
        maxQueue.add(value);
    }

    public int pop_front() {
        if (queue.isEmpty()){
            return -1;
        }
//         如果要弹出的值与队列当前最大值相等, 那么就将这个值从当前最大值队列中删除
        int ans = queue.poll();
        if (ans == maxQueue.peekFirst()){
            maxQueue.pollFirst();
        }
        return ans;
    }
}
